class Node:
    def __init__(self,val=None,key=None,next=None,pre=None):
        self.val=val 
        self.key=key
        self.next=next 
        self.pre=pre 

class LRUCache:
    def __init__(self,capacity):
        self.capacity=capacity
        self.hash={} #key:node
        self.head=Node()
        self.tail=Node() 
        self.head.next=self.tail #**
        self.tail.pre=self.head

    def move2end(self,key):
        node=self.hash[key]
        node.pre.next=node.next 
        node.next.pre=node.pre 
        self.tail.pre.next=node 
        node.pre=self.tail.pre 
        node.next=self.tail 
        self.tail.pre=node 

    def get(self,key):
        k=self.hash.get(key,-1)
        if k==-1: return -1 
        else: 
            self.move2end(key)
            return k.val 

    def put(self,lst):
        k,v=lst[0],lst[1]
        if k in self.hash:
            self.hash[k].val=v 
            self.move2end(k) #**
        else:
            if len(self.hash)==self.capacity:
                self.hash.pop(self.head.next.key)
                self.head.next=self.head.next.next 
                self.head.next.pre=self.head #**
            new_node=Node(key=k,val=v)
            self.hash[k]=new_node
            self.tail.pre.next=new_node 
            new_node.pre=self.tail.pre 
            new_node.next=self.tail 
            self.tail.pre=new_node 

def solve(lst1,lst2):
    lru=LRUCache(lst2[0][0])
    ans=[]
    for i in range(1,len(lst1)):
        if lst1[i]=="put":
            lru.put(lst2[i])
            ans.append(None)
        if lst1[i]=="get":
            ans.append(lru.get(lst2[i][0]))
    return ans 

lst1=["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
lst2=[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
print(solve(lst1,lst2))


